The sequence of triangle numbers is generated by adding the natural numbers. So the 7th triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:
1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...
Let us list the factors of the first seven triangle numbers:
1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28
We can see that 28 is the first triangle number to have over five divisors.
What is the value of the first triangle number to have over five hundred divisors?
In [1]:
N = 100000
divisors = [1] * N
tiny_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23]
small_primes = tiny_primes
for n in range(25, 500, 2):
for p in tiny_primes:
if n % p == 0:
break
else:
small_primes.append(n)
for n in range(2, N):
for p in small_primes:
if n % p == 0:
m = n // p
q = 2
while m % p == 0:
q += 1
m //= p
divisors[n] = divisors[m] * q
break
else:
divisors[n] = 2
def T(n):
if n % 2 == 0:
return divisors[n//2] * divisors[n+1]
else:
return divisors[n] * divisors[(n+1)//2]
for n in range(1, N):
if T(n) > 500:
print(n*(n+1)//2)
break
Explanation: Let $d(n)$ denote the number of divisors of $n$. If $p$ is any prime divisor of $n$, then we can write $n$ uniquely as $n = p^k m$ where $p$ does not divide $m$. Each divisor of $n$ has the form $p^i r$, where $0 \le i \le k$ and $r$ divides $m$. There are $k+1$ options for $i$, and $d(r)$ options for $r$. Therefore, $d(n) = (k+1) d(r)$.
We wish to calculate the number of divisors of the $n$-th triangular number $T(n) = n(n+1)/2$. If $n$ is even, then every divisor of $T(n)$ can be expressed uniquely as the product of a divisor of $n/2$ and a divisor of $n+1$, since $n/2$ and $n+1$ are relatively prime. If $n$ is odd, then every divisor of $T(n)$ can be expressed uniquely as the product of a divisor of $n$ and a divisor of $(n+1)/2$, since $n$ and $(n+1)/2$ are relatively prime. Therefore, $d(T(n)) = d(n/2) d(n+1)$ if $n$ is even, but $d(T(n)) = d(n) d((n+1)/2)$ if $n$ is odd.